/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/product-of-array-exclude-itself
   @Language: C++
   @Datetime: 16-02-09 05:15
   */

class Solution {
public:
	/**
	 * @param A: Given an integers array A
	 * @return: long long array B
	 *          and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
	 */
	/** Method 1, Need Space O(n) but easy to understand
	 * Tisp:
	 * asuming : array L[i] = A[0] * A[1] *...*A[i-1]
	 *           array R[i] =A[n-1]*A[n-2]*...*A[i+1]
	 *           we define L[0] = R[n-1] = 1
	 * so array B[i] = L[i] * R[i]
	 * */
	vector<long long> productExcludeItself(vector<int> &A) {
		// write your code here
		vector<long long> B(A.size(),1);
		if (B.size() < 1) return B;
		vector<long long> L(A.size(),1), R(A.size(),1);
		for(int i=0; ++i<A.size(); L[i]=L[i-1]*A[i-1]);
		for(int i=A.size()-1; i--; R[i]=R[i+1]*A[i+1]);
		for(int i=A.size(); i--; B[i]=L[i]*R[i]);
		return B;
	}

	/** Method 2, State Compression for array R
	 * at Method 1 line 30, i decrease from n-1 to 0
	 * when calculate B[i]:
	 * we do not need the R[i+1], R[i+2], R[n-1], only need current R[i].
	 * so only use 1 space to store current R[i]
	 *
	 * Asuming : array L[i]= A[0]*A[1]*...*A[i-1]
	 *                 R[i] = R[i-1]*A[i-1]
	 * array B[i] = L[i] * R[i]
	 * */
	vector<long long> productExcludeItself(vector<int> &A) {
		// write your code here
		vector<long long> B(A.size(),1);
		if (B.size() < 1) return B;
		vector<long long> L(A.size(),1);
		long long R=1;
		for(int i=0; ++i<A.size(); L[i]=L[i-1]*A[i-1]);
		for(int i=A.size(); i--; B[i]=L[i]*R, R*=A[i]);
		return B;
	}

	/** Method 3, Only need O(1) another space
	 * Tips: State Compression for Dynamic Programming
	 * at Method 2 line 51, when calculate B[i]:
	 * we do not need the L[i-1], L[i-2], or L[i+1], L[i+2]. only need current L[i].
	 * so, use B[i] to store L[i] frist, then calculate B[i] TWICE!
	 *
	 * first : array B[i]= A[0]*A[1]*...*A[i-1], like Method 1/2 array L
	 * second:       B[i]=B[i]*R,  R is like Method 2
	 *                   R[i] = R[i-1]*A[i-1]
	 * */
	vector<long long> productExcludeItself(vector<int> &A) {
		// write your code here
		vector<long long> B(A.size(),1);
		if (B.size() < 1) return B;
		long long R=1;
		for(int i=0; ++i<A.size(); B[i]=B[i-1]*A[i-1]);
		for(int i=A.size(); i--; B[i]*=R, R*=A[i]);
		return B;
	}
};
